This application claims priority to Korean Patent Application No. 2002-45975, filed on Aug. 3, 2002, which is herein incorporated by reference in its entirety.
1. Field of the Invention
The present invention relates to a decoding apparatus, and more particularly, to an apparatus and method for decoding variable length coded data.
2. Description of the Related Art
The Moving Picture Experts Group (MPEG)2 standard, published in April of 1994, is an international standard for the compression and decompression of video.
Methods of compressing and decompressing video have been increasingly used in various applications such as for the transmission of digital image data and for digital storage devices. Image compression algorithms typically perform lossless compression of image data using a variable length encoder.
The variable length encoder assigns shorter bits to data symbols having a relatively high probability of occurrence and longer bits to data symbols having a relatively low probability of occurrence. Accordingly, when encoding a given data bitstream, the variable length encoder generates a shorter data bitstream than a fixed length encoder.
The variable length decoder detaches a variable length code corresponding to a single symbol from an input variable length coded data bitstream and obtains a fixed length code from the detached variable length code using a symbol table. If a variable length coding table used in the variable length encoder can be set by a user, the variable length decoder detaches variable length codes while reading fixed-length bits from an input data bitstream based on the variable length coding table used in the variable length encoder.
A method of detaching bits from an input data bitstream one by one and performing a tree search algorithm on each bit is a fundamental variable length decoding method. In the case of an MPEG bitstream, a typical maximum code length is 16 bits. For a code length of 16 bits, 16 tree searches need to be performed to obtain a code value. In another method, bits are detached in groups of two from an input data bitstream and a tree search algorithm is performed on each group of two bits. In this method, 8 tree searches need to be performed to obtain a code value given a code length of 16 bits.
As the number of bits detached from a data bitstream increases, decoding speed increases, but the structure of a decoder becomes increasingly complicated. Accordingly, an appropriate trade-off between decoding speed and the complexity of a decoder is needed.
Therefore, a need exists for a variable length decoder capable of handling a plurality of codes simultaneously.
The present invention provides an apparatus for decoding a variable length code, wherein L bits are detached from an input data bitstream and decoded. Pre-decoding methods are selectively used according to a characteristic of a code value of the input data bitstream.
The present invention provides a method of decoding a variable length code, wherein L bits are detached from an input data bitstream and decoded. Pre-decoding methods are selectively used according to a characteristic of a code value of the input data bitstream.
According to an embodiment of the present invention, there is provided an apparatus for decoding a variable length code comprising a pre-decoding unit, a shifter, first through M-th look-up table address registers, a selector, a memory controller, a memory, and a memory searcher. The pre-decoding unit receives a data bitstream and generates a first selection signal or a second selection signal for selecting a look-up table address register from a set of first through M-th look-up table address registers according to a code value of the data bitstream, where M is a natural number. The shifter shifts the data bitstream by a predetermined number of bits in response to one of the first selection signal and the second selection signal and a predetermined continuous node signal. Each of the first through M-th look-up table address registers includes a LOC (Local Codes) address designating a K-bit LOC table value stored in a memory, where K is a natural number. The selector selects an output of the first through M-th look-up table address registers and outputs the selected output in response to one of the first selection signal and the second selection signal. The memory controller receives the output of the selector, generates a third selection signal for selecting a LOC table value and a terminal value corresponding to the LOC table value in response to the predetermined continuous node signal, or generates a fourth selection signal for selecting a predetermined fixed length code stored in the memory in response to a predetermined symbol address signal, where the LOC table value and the terminal value are stored in the memory, and the terminal value is used to obtain a predetermined symbol address. The memory stores LOC table values, terminal values, and fixed length codes, outputs a LOC table value and a terminal value in response to the third selection signal, and outputs a fixed length code in response to the fourth selection code. The memory searcher receives the LOC table value and the terminal value that are output from the memory and L bits of the data bitstream, determines whether the L bits of the data bitstream designate a terminal node or a continuous node using a LOC information table stored therein, generates a continuous node signal or a symbol address signal based on the result of the determination, receives the fixed length code output from the memory, and outputs the fixed length code, where L is a natural number.
The pre-decoding unit includes a first pre-decoder and a second pre-decoder. The first pre-decoder receives the data bitstream and when sequential 0s or 1s exist in a set of most significant bits (MSBs) of the data bitstream, generates the first selection signal for selecting the look-up table address register from the set of first through M-th look-up table address registers according to the number of sequential 0s or 1s. The second pre-decoder receives the data bitstream and generates the second selection signal for selecting the look-up table address register from the set of first through M-th look-up table address registers using N bits in the MSBs of the data bitstream, where N is a natural number.
The shifter shifts the data bitstream by 3 bits in response to the continuous node signal.
The memory controller includes an offset register, an adder, a LOC address register, and a symbol address register. The offset register receives the output of the selector and stores it until a next output is received from the selector. The adder generates the third selection signal for selecting values from a LOC table stored in the memory by adding the output of the offset register and a predetermined next LOC address. The LOC address register generates the predetermined next LOC address in response to the continuous node signal. The symbol address register generates the fourth selection signal for selecting the fixed length code in response to the symbol address signal.
The next LOC address is a sum of a current LOC address and a number of non-terminal nodes in a current LOC up to a current node.
The symbol address is a sum of a terminal value corresponding to a current LOC table value and a number of terminal nodes in a current LOC before a current node.
The LOC information table stored in the memory searcher includes node types indicating whether a node designated by the variable length code is a terminal node, a continuous node, or an invalid node, each node type comprising N*2L LOC information bits, and LOC information bits for each node type are expressed using four formats A, B, C, and D. Each format comprises N bits.
In the LOC information table stored in the memory searcher, a node type designated by the variable length code is a terminal node when the variable length code is 0, 1, 00, 01, 10, or 11, and a node type designated by the variable length code is one of the terminal node, the continuous node, and the invalid node when the variable length code is one of 000 through 111. Here, in a case where N is 2 and L is 3, when the variable length code is 0, an upper 8 bits of the LOC information bits are expressed as ABBB. When the variable length code is 1, a lower 8 bits of the LOC information bits are expressed as ABBB. When the variable length code is 00, an upper 4 bits of the LOC information bits are expressed as AB. When the variable length code is 01, LOC information bits from an upper fifth to eighth places are expressed as AB. When the variable length code is 10, LOC information bits from an upper ninth to twelfth places are expressed as AB. When the variable length code is 11, LOC information bits from an upper thirteenth to sixteenth places are expressed as AB. When the variable length code is one of 000 through 111, LOC information bits for a terminal node designated by the variable length code are expressed as A, LOC information bits for a continuous node designated by the variable length code are expressed as C, and LOC information bits for an invalid node designated by the variable length code are expressed as D.
In the LOC information table stored in the memory searcher, a node type designated by the variable length code is the terminal node when the variable length code is 0 or 1, and a node type designated by the variable length code is one of the terminal node, the continuous node, and the invalid node when the variable length code is one of 00 through 11. Here, in a case where N is 2 and L is 2, when the variable length code is 0, the upper 4 bits among LOC information bits are expressed as AB. When the variable length code is 1, a lower 4 bits among LOC information bits are expressed as AB. When the variable length code is one of 00 through 11, LOC information bits for a terminal node designated by the variable length code are expressed as A, LOC information bits for a continuous node designated by the variable length code are expressed as C, and LOC information bits for an invalid node designated by the variable length code are expressed as D.
Each LOC table value stored in the memory comprises LOC information bits corresponding to node types designated by each variable length code of a current LOC in the LOC information table.
According to another embodiment of the present invention, there is provided a method of decoding a variable length code using a variable length code decoding apparatus, which includes first through M-th look-up table address registers each including a predetermined LOC address; a memory storing a LOC table, which comprises K-bit LOC table values corresponding to each LOC address and predetermined terminal values corresponding to each LOC address, and fixed length codes; and a memory searcher storing a LOC information table comprising information referred to for decoding a variable length code, where M is a natural number and K is a natural number. The method includes (a) receiving a data bitstream and generating one of a first selection signal and a second selection signal for selecting a look-up table address register from a set of first through M-th look-up table address registers according to a code value of the data bitstream; (b) selecting an output of the first through M-th look-up table address registers in response to one of the first selection signal and the second selection signal; (c) generating a third selection signal for selecting a LOC table value and a terminal value corresponding to the LOC table value from the LOC table stored in the memory by adding the output selected in (b) and a predetermined next LOC address, the terminal value being used to obtain a predetermined symbol address; (d) selecting a LOC table value and a terminal value from the LOC table in response to the third selection signal; (e) determining whether L bits of the data bitstream designates a terminal node or a continuous node using the LOC information table based on the selected LOC table value and the selected terminal value, which are output from the memory, to generate a continuous node signal or a symbol address signal, wherein L is a natural number; (f) generating the predetermined next LOC address used for selecting the LOC table value in response to the continuous node signal; (g) generating a fourth selection signal for selecting a fixed length code in response to the symbol address signal; and (h) selecting a fixed length code from the memory and outputting the fixed length code, in response to the fourth selection signal.
Receiving a data bitstream and generating one of the first selection signal and the second selection signal for selecting the look-up table address register from the set of first through M-th look-up table address registers according to a code value of the data bitstream comprises, (a1) when sequential 0s or 1s exist in a set of most significant bits (MSBs) of the data bitstream, generating the first selection signal for selecting the look-up table address register from the set of first through M-th look-up table address registers according to the number of sequential 0s or 1s; (a2) generating the second selection signal for selecting the look-up table address register from the set of first through M-th look-up table address registers using N bits in the MSBs of the data bitstream, wherein N is a natural number; and (a3) shifting the data bitstream by a predetermined number of bits in response to one of the first selection signal and the second selection signal and the continuous node signal.
The next LOC address is a sum of a current LOC address and a number of non-terminal nodes in a current LOC up to a current node.
The symbol address is a sum of a terminal value corresponding to a current LOC table value and a number of terminal nodes in a current LOC before a current node.
The LOC information table stored in the memory searcher includes node types indicating whether a node designated by a variable length code is a terminal node, a continuous node, or an invalid node, each node type comprising N*2L LOC information bits, and LOC information bits for each node type are expressed using four formats A, B, C, and D. Each format comprising N bits.
Each LOC table value stored in the memory comprises LOC information bits corresponding to node types designated by each variable length code of a current LOC in the LOC information table.